package leetcode.L34;

class Solution1 {
    public int[] searchRange(int[] nums, int target) {
        /*
        method 1:
        直接找等于的，但是针对等于的情况，mid+1表示为找到右边界，mid-1表示找到左边界。
         */
        /*
        method 2:
        二分查找直接搜索边界
         */
        int leftIndex = -1;
        int rightIndex = -1;
        boolean flag = true;
        leftIndex = binarySearch(nums, target, flag);
        flag = false;
        rightIndex = binarySearch(nums, target, flag) - 1;//做判断是否合法

        if (rightIndex < 0 || leftIndex < 0 || leftIndex > rightIndex) {
            return new int[]{-1, -1};
        }
        return new int[]{leftIndex, rightIndex};
    }

    public int binarySearch(int[] nums, int target, boolean flag) {
        int low = 0;
        int high = nums.length - 1;
        int ans = nums.length;//为了杜绝数组长度只有1的情况
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] > target || (flag && nums[mid] >= target)) {//这里取严格大于是为了找到值大于target的下一个为位置的值
                high = mid - 1;
                ans = mid;//保存大于target的最小值
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}